package com.zhouxianglh.p39;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Objects;

/**
 * 39. 组合总和
 *
 * @author zhouxianglh
 */
public class Solution {
    public static void main(String[] args) {
        System.out.println(combinationSum(new int[]{2, 3, 6, 7}, 7));
        System.out.println(combinationSum(new int[]{2, 3, 5}, 8));
        System.out.println(combinationSum(new int[]{2}, 1));
    }

    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> count = count(candidates, target, candidates[0]);
        return Objects.requireNonNullElseGet(count, ArrayList::new);
    }

    public static List<List<Integer>> count(int[] candidates, int target, int pre) {
        List<List<Integer>> lists = null;
        for (int i : candidates) {
            if (pre > i) {
                continue;
            }
            int value = target - i;
            if (value == 0) {
                if (null == lists) {
                    lists = new ArrayList<>();
                }
                List<Integer> list = new ArrayList<>();
                list.add(i);
                lists.add(list);
            } else if (value > 0) {
                List<List<Integer>> listList = count(candidates, value, i);
                if (null != listList) {
                    listList.forEach(list -> list.add(i));
                    if (null == lists) {
                        lists = listList;
                    } else {
                        lists.addAll(listList);
                    }
                }
            }
        }
        return lists;
    }
}
